/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/search-a-2d-matrix-ii
   @Language: C++
   @Datetime: 16-02-09 08:28
   */

class Solution {
public:
	/**
	 * @param matrix: A list of lists of integers
	 * @param target: An integer you want to search in matrix
	 * @return: An integer indicate the total occurrence of target in the given matrix
	 */
	/** Tips: each row and column are sorted in ascending order
	 * we can search from left bottom to right top ;
	 * or search from right top to left bottom.
	 * this method below is searching from left bottom to right top
	 * */
	int searchMatrix(vector<vector<int> > &M, int t) {
		// write your code here
		int c=0;	// for more robust, using size() to get length
		for(int i=M.size()-1, j=0;i>-1 && j<M[i].size();){
			if (M[i][j] > t) --i;
			else if (M[i][j] < t) ++j;
			else{   // if has no duplicate integers, remove below two fors
				for(int k=j+1; k<M[i].size() && t==M[i][k++]; ++c);
				for(int k=i-1; k>-1 && t==M[k--][j]; ++c);
				--i,++j,++c;
			}
		}
		return c;
	}
};
